// const arr = [57,68,59,30,45,24,55,34];

// const quick = (arr,i,j) => {
//     let key = arr[i];
//     while( i < j ) {
//         while( arr[j] >= key) {
//             j--;
//         }
//         arr[i] = arr[j];
//         while( arr [i] <= key){
//             i++;
//         }
//         arr[j]=arr[i];
//     }
//     arr[i] = key;
//     return i;
// }

// const quickSort = (arr,i,j) => {
//     if(i < j){
//         let pindex = quick(arr,i,j);
//         quickSort(arr, i, pindex-1);
//         quickSort(arr,pindex + 1,j)
//     }
//     return arr;
// }

// console.log(quickSort(arr,0,arr.length -1));
// 快排
const arr = [15,12,3,2,7];  
const quickSort = (arr) => {
    if(arr.length <= 1) {
        return arr;
    }
    // let min = Math.floor(arr.length / 2);
    let min = arr.length >> 1;
    let index = arr.splice(min,1)[0];
    const left = [];
    const right = [];
    for(let i = 0;i < arr.length; i++) {
        if(arr[i] < index){
            left.push(arr[i])
        }else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([index],quickSort(right))
}

console.log(quickSort(arr));

// arr.length >> 1是一个位运算符，表示将数组长度的二进制表示向右移动一位，相当于将长度除以2并向下取整。
// 这种语法通常用于对数组进行二分查找、排序或分割等操作时，作为计算数组中间值的便捷方法。

const  quick = (arr) => {
    if (arr.length <= 1) return arr;
    // let index = Math.floor(arr.length / 2);
    let index = arr.length >> 1
    let min = arr.splice(index,1)[0];
    const left = [];
    const right = [];
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < min) {
            left.push(arr[i])
        }else {
            right.push(arr[i]);
        }
    }
    return quick(left).concat([min],quick(right))
}
// console.log(quick(arr));